//
// Created by zx208 on 2024/10/17.
//

// 已知单链表递增 试设计一个高效的算法，
// 删除表中所有值大于mink且小于maxk的元素
// 同时释放被删除的结点空间

#include "../SingleLinkedList.h"

LinkedList Create_List_R(LinkedList head, int n){

    // 先创建头指针
    head = (LinkedList) malloc(sizeof( LNode));
    head->next = NULL;

    // 创建一个工作指针
    LinkedList node = head;

    for (int i = 0; i < n; ++i) {
        LinkedList p = (LinkedList) malloc(sizeof( LNode));
        int data;
        scanf(" %d", &data);
        p->data = data;
        p->next = node->next; // 即 p->next = NULL;
        node->next = p;
        node = p;
    }
    return head;
}

void PrintLL(LinkedList L){
    LNode *node = L->next;
    while(node){
        printf("%d ", node->data);
        node = node->next;
    }
}

Status Delete_Interval_LL(LinkedList L, ElemType mink, ElemType maxk){
    LinkedList p = L, tmp;

    // mink和maxk不合理
    if(mink > maxk) return ERROR;

    while(p->next){
        if(p->next->data < mink || p->next->data > maxk){
            tmp = p->next;
            p->next = p->next->next;
            free(tmp);
        }else p = p->next;
    }
    return OK;
}

int main(void){
    LinkedList L = NULL;
    ElemType mink, maxk;
    Status provided;
    L = Create_List_R(L, 5);
    scanf("%d%d", &mink, &maxk);
    provided = Delete_Interval_LL(L, mink, maxk);
    if(provided) PrintLL(L);
    return 0;
}

// 1 2 3 4 5
// 2 4